병렬 알고리즘

공유 메모리 모델은 병렬 프로그래밍의 주요 모델 중 하나로, 여러 프로세서나 스레드가 하나의 공통된 메모리 공간을 공유하여 데이터에 접근하는 방식을 말한다. 이 모델에서 각 처리 요소는 독립적으로 명령어를 실행할 수 있지만, 모든 데이터에 대한 접근은 동일한 논리적 메모리 주소 공간을 통해 이루어진다. 이로 인해 데이터 교환을 위한 명시적인 통신 메시지가 필요 없으며, 대신 메모리 위치를 읽고 쓰는 방식으로 데이터를 공유한다.

이 모델의 대표적인 추상 기계는 PRAM이다. PRAM은 무한한 수의 프로세서가 하나의 공유 메모리에 접근한다는 이상적인 모델로, 메모리 접근 충돌 방식에 따라 여러 변형이 존재한다. 실제 하드웨어에서는 멀티코어 프로세서 기반의 시스템이 이 모델을 구현하는 대표적인 예이다.

공유 메모리 모델의 주요 장점은 프로그래밍의 편의성이다. 전역 메모리 공간을 공유하기 때문에 데이터 배분과 통신에 대한 복잡한 관리가 줄어들고, 직렬 프로그램을 병렬화하기가 상대적으로 용이하다. 그러나 여러 스레드가 동시에 같은 데이터를 수정하려 할 때 발생하는 경쟁 상태를 방지하기 위해 동기화 메커니즘(예: 뮤텍스, 세마포어)이 필수적이며, 이로 인한 오버헤드와 데드락 가능성은 중요한 도전 과제가 된다.

이 모델은 데이터 의존성이 강하거나 불규칙한 데이터 접근 패턴을 보이는 알고리즘보다는, 반복적이고 규칙적인 계산이 많은 응용 분야에 효과적이다.

분산 메모리 모델은 각 프로세서가 자신만의 독립적인 메모리를 가지는 병렬 컴퓨팅 구조이다. 프로세서 간의 데이터 교환은 명시적인 메시지 전송을 통해 이루어지며, 이는 네트워크나 상호 연결망을 통해 수행된다. 이 모델은 물리적으로 분리된 여러 컴퓨터 노드로 구성된 클러스터나 대규모 병렬 처리 시스템에서 주로 사용된다. 프로세서 간 통신은 프로그래머가 직접 관리해야 하므로, 통신 지연과 대역폭이 알고리즘 성능에 중요한 영향을 미친다.

분산 메모리 시스템의 대표적인 프로그래밍 인터페이스는 MPI이다. MPI는 메시지 전송을 위한 표준 라이브러리로, 송신과 수신 연산을 통해 프로세스 간 데이터를 교환한다. 이 모델에서 데이터는 일반적으로 각 프로세스에 고르게 분배되며, 프로세스는 자신의 로컬 메모리에 있는 데이터를 처리한다. 계산 중간에 다른 프로세스의 데이터가 필요하면 메시지 통신을 요청해야 한다.

분산 메모리 모델의 주요 장점은 확장성이 뛰어나다는 점이다. 프로세서 수를 늘려도 공유 메모리 경쟁이나 일관성 문제가 발생하지 않는다. 또한 각 노드가 표준 컴퓨터로 구성될 수 있어 하드웨어 비용이 상대적으로 낮다. 반면, 통신 오버헤드가 크고 프로그래밍 복잡도가 높다는 단점이 있다. 알고리즘 설계 시 계산 작업을 분배하는 것뿐만 아니라 통신 패턴과 데이터 분배를 신중하게 고려해야 한다.

이 모델은 대규모 과학기술 계산, 기상 예측, 분자 모델링 등 방대한 데이터를 처리하는 문제에 적합하다. 통신 비용을 최소화하기 위해 데이터 지역성을 높이고, 통신과 계산을 중첩시키는 등의 최적화 기법이 중요하게 적용된다.

데이터 병렬 모델은 병렬 알고리즘 설계의 주요 패러다임 중 하나로, 동일한 연산을 여러 데이터 요소에 대해 동시에 수행하는 데 초점을 둔다. 이 모델은 특히 규모가 크고 구조가 균일한 데이터 집합을 처리할 때 효과적이다. 핵심 아이디어는 데이터를 여러 부분으로 분할하고, 각 부분을 서로 다른 처리 장치에 할당하여 병렬로 처리한 후, 결과를 다시 통합하는 것이다. 이 접근 방식은 SIMD(단일 명령어 다중 데이터) 아키텍처와 잘 맞으며, GPU 컴퓨팅의 기본 원리이기도 하다.

이 모델의 전형적인 예는 대규모 배열이나 행렬에 대한 연산이다. 예를 들어, 두 개의 큰 벡터를 더하는 작업은 각 벡터를 여러 조각으로 나누고, 각 코어나 프로세서가 자신에게 할당된 조각들에 대한 덧셈을 동시에 수행하도록 할당함으로써 병렬화할 수 있다. 데이터 병렬성의 성공은 데이터를 얼마나 균등하게 분할할 수 있는지, 그리고 처리 장치 간의 동기화와 통신 오버헤드를 최소화할 수 있는지에 크게 의존한다.

데이터 병렬 모델을 구현하는 데 널리 사용되는 도구로는 OpenCL과 CUDA가 있다. 이러한 프레임워크는 개발자가 데이터 병렬 커널을 작성하여 수천 개의 스레드가 구조화된 데이터를 병렬로 처리하도록 할 수 있다. 데이터 병렬 모델의 주요 장점은 작업 부하가 데이터 분할에 의해 자연스럽게 결정되어 부하 균형 문제가 상대적으로 덜 발생할 수 있다는 점이다. 그러나 모든 알고리즘이 이 모델에 적합한 것은 아니며, 데이터 요소 간에 강한 의존성이 있거나 처리 패턴이 불규칙한 경우에는 적용하기 어려울 수 있다.

태스크 병렬 모델은 병렬 알고리즘을 설계하는 주요 패러다임 중 하나이다. 이 모델은 전체 계산 작업을 여러 개의 독립적이거나 약하게 연결된 하위 작업, 즉 태스크로 분해하는 데 초점을 맞춘다. 이렇게 생성된 태스크들은 서로 다른 프로세서나 코어에 할당되어 가능한 한 동시에 실행된다. 핵심 목표는 작업을 효율적으로 분할하여 병렬 처리의 이점을 최대화하는 것이다.

이 모델의 설계에는 몇 가지 일반적인 패턴이 사용된다. 대표적인 예로 분할 정복 기법이 있는데, 큰 문제를 재귀적으로 더 작은 하위 문제로 나누고, 각 하위 문제를 병렬로 해결한 후 그 결과를 결합한다. 또 다른 패턴은 파이프라이닝으로, 일련의 처리 단계를 구성하고 각 단계가 서로 다른 데이터에 대해 동시에 작업하도록 한다. 작업 풀 패턴은 실행할 태스크들을 중앙 큐에 넣고 유휴 상태의 워커들이 큐에서 태스크를 가져와 실행하는 방식으로 동작한다.

태스크 병렬 모델은 공유 메모리와 분산 메모리 시스템 모두에 적용될 수 있지만, 구현 방식은 다르다. 공유 메모리 환경에서는 스레드가 메모리를 공유하며 태스크를 실행하고, 동기화는 뮤텍스나 세마포어 같은 기법으로 관리된다. 반면, 분산 메모리 환경에서는 메시지 전달 인터페이스(MPI)와 같은 라이브러리를 사용하여 태스크를 여러 머신에 분배하고 통신해야 한다.

이 모델의 성공은 태스크를 얼마나 균등하게 분배하고 태스크 간 의존성을 어떻게 관리하느냐에 크게 좌우된다. 부하 불균형은 일부 프로세서가 유휴 상태가 되는 원인이 되어 성능을 저하시킨다. 또한 태스크 간에 데이터 의존성이 존재하면, 이를 해결하기 위한 동기화로 인해 대기 시간이 발생할 수 있어 설계 시 주의가 필요하다.

분할 정복은 병렬 알고리즘 설계의 기본 기법 중 하나이다. 이 기법은 문제를 여러 개의 독립적이거나 거의 독립적인 하위 문제로 재귀적으로 분할하고, 각 하위 문제를 병렬로 해결한 후, 그 결과를 결합하여 최종 답을 얻는다. 순차 알고리즘에서도 널리 사용되는 패러다임이지만, 병렬 처리에서는 하위 문제들을 동시에 처리할 수 있다는 점에서 큰 잠재력을 발휘한다.

분할 정복 알고리즘의 병렬 실행은 일반적으로 재귀 트리 구조를 따른다. 최상위 노드에서 문제가 분할되면, 생성된 하위 문제들은 서로 다른 프로세서나 스레드에 할당되어 병렬로 처리된다. 이 과정은 각 하위 문제가 충분히 작아질 때까지(기저 사례에 도달할 때까지) 반복된다. 병렬 분할 정복의 효율성은 하위 문제들 사이의 의존성이 적고, 작업량이 고르게 분배될 수 있을 때 극대화된다.

대표적인 병렬 분할 정복 알고리즘의 예는 병렬 정렬 알고리즘이다. 예를 들어, 병렬 합병 정렬은 배열을 반으로 나누는 분할 단계 후, 두 개의 하위 배열에 대한 정렬 작업을 독립적으로 병렬 수행한다. 이후 두 개의 정렬된 하위 배열을 합치는 결합 단계를 거친다. 병렬 퀵 정렬 또한 피벗을 기준으로 분할된 부분 배열들을 동시에 정렬하는 방식으로 구현될 수 있다.

분할 정복 접근법의 성공은 문제 분할의 균형과 프로세서 간 통신 또는 동기화 오버헤드를 어떻게 관리하느냐에 달려있다. 이상적으로는 작업이 균등하게 분배되어 모든 프로세서가 유사한 시간 동안 바쁘게 유지되어야 한다. 또한, 하위 문제를 결합하는 단계에서 발생할 수 있는 병목 현상을 최소화하는 설계가 중요하다.

동적 프로그래밍은 큰 문제를 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산을 피하는 알고리즘 설계 기법이다. 병렬 알고리즘 설계에서 동적 프로그래밍을 적용할 때는 하위 문제 간의 의존성을 분석하여 독립적으로 계산 가능한 부분을 찾아내고, 이를 여러 프로세서에 분배하여 동시에 처리하는 방식이 핵심이다. 예를 들어, 행렬 체인 곱셈이나 최장 공통 부분 수열 문제에서 DP 테이블을 채우는 순서를 재구성하면 병렬 실행이 가능해진다.

병렬 동적 프로그래밍의 구현은 주로 하위 문제들 간의 데이터 의존성 그래프를 기반으로 한다. 의존성이 없는, 즉 서로 독립적인 하위 문제들은 동시에 계산될 수 있다. 이를 위해 작업 스케줄링 기법이 사용되며, 공유 메모리 모델에서는 스레드 풀을, 분산 메모리 모델에서는 메시지 전달을 활용하여 작업을 분배한다. DP 테이블의 업데이트 순서를 병렬화에 적합하게 설계하는 것이 중요하다.

그러나 모든 동적 프로그래밍 문제가 효율적으로 병렬화되는 것은 아니다. 하위 문제 간의 의존성이 강한 경우, 예를 들어 대각선 방향으로만 진행되는 DP에서는 병렬 처리의 폭이 제한될 수 있다. 따라서 병렬 알고리즘 설계 시에는 문제의 고유한 의존성 구조를 파악하고, 이를 극복할 수 있는 새로운 DP 상태 정의나 계산 순서를 모색해야 한다.

파이프라이닝은 작업을 여러 개의 순차적 단계로 나누고, 각 단계를 서로 다른 처리 장치가 동시에 처리하도록 하는 병렬 알고리즘 설계 기법이다. 이 방식은 공장의 생산 라인과 유사하게, 한 작업이 첫 번째 단계를 통과하면 다음 작업이 바로 그 첫 단계에 들어갈 수 있어, 전체적으로 여러 작업이 서로 다른 단계에서 동시에 진행된다. 이를 통해 작업 처리의 처리량을 높이고 지연 시간을 숨길 수 있다.

파이프라이닝의 효과는 각 단계의 처리 시간이 균등할 때 최대화된다. 만약 한 단계가 다른 단계보다 훨씬 느리다면, 그 단계가 병목 현상이 되어 전체 처리 속도를 저하시킨다. 따라서 파이프라인을 설계할 때는 작업을 균형 있게 분할하고 단계 간의 데이터 전달을 효율적으로 관리하는 것이 중요하다.

이 기법은 특히 명령어 파이프라인, 그래픽스 렌더링 파이프라인, 그리고 대규모 데이터 처리 워크플로우에서 널리 적용된다. 예를 들어, CPU는 명령어를 인출, 해독, 실행, 쓰기 등의 단계로 나누어 파이프라이닝함으로써 성능을 크게 향상시킨다.

분산 탐색은 병렬 알고리즘 설계 기법 중 하나로, 큰 탐색 공간을 여러 작업자(프로세서나 스레드)가 나누어 동시에 탐색하는 방식을 말한다. 주로 상태 공간 탐색, 조합 최적화 문제, 게임 트리 탐색 등에서 활용된다. 예를 들어, 체스나 바둑 같은 게임에서 가능한 모든 수를 평가하거나, 미로 찾기 문제에서 모든 경로를 찾는 경우에 적용할 수 있다. 이 기법의 핵심은 탐색 트리나 그래프를 여러 부분으로 분할하여 각 부분을 병렬로 처리함으로써 전체 실행 시간을 단축하는 것이다.

분산 탐색을 구현하는 일반적인 방법은 작업 풀 모델을 사용하는 것이다. 초기 탐색 작업(예: 루트 노드)을 작업 큐에 넣고, 사용 가능한 작업자들이 큐에서 작업을 가져와 수행한다. 각 작업자는 자신에게 할당된 노드를 확장하여 새로운 자식 노드들을 생성하고, 이 중 추가 탐사가 필요한 노드들을 다시 작업 큐에 넣는다. 이 과정은 탐색이 완료될 때까지 반복된다. 이때 작업자 간의 통신과 조정이 필요하며, 특히 분산 메모리 시스템에서는 메시지 전달 인터페이스를 사용하여 작업을 분배한다.

분산 탐색의 성능은 부하 균형과 작업 중복 관리에 크게 의존한다. 작업을 고르게 분배하지 못하면 일부 작업자는 빨리 일을 마치고 유휴 상태가 되는 반면, 다른 작업자는 많은 작업을 처리하게 되어 전체 효율이 떨어진다. 또한, 서로 다른 작업자가 동일한 상태를 중복해서 탐색하지 않도록 주의해야 한다. 이를 해결하기 위해 동적 작업 할당 전략이나 중복 상태 검출을 위한 해시 테이블 공유 등의 기법이 사용된다. 분산 탐색은 문제의 규모가 클수록, 그리고 탐색 공간을 효율적으로 분할할수록 병렬 처리의 이점을 극대화할 수 있다.

병렬 알고리즘의 성능을 평가하는 가장 기본적인 척도는 속도 향상이다. 속도 향상은 특정 문제를 해결하는 데 걸리는 순차 알고리즘의 실행 시간과, 동일한 문제를 해결하는 병렬 알고리즘의 실행 시간의 비율로 정의된다. 즉, 병렬화를 통해 작업을 얼마나 빠르게 완료할 수 있는지를 수치화한 것이다. 이상적인 경우, 프로세서(코어) 수를 p배 늘리면 실행 시간도 1/p배로 줄어들어 속도 향상이 p배가 되어야 하지만, 실제로는 여러 요인으로 인해 이 이상적인 선형 속도 향상을 달성하기는 어렵다.

속도 향상을 계산하는 일반적인 공식은 다음과 같다.

속도 향상이 선형에 미치지 못하는 주된 원인은 알고리즘의 순차적 부분, 프로세서 간 통신 및 동기화에 따른 오버헤드, 그리고 작업 부하의 불균형 때문이다. 예를 들어, 전체 작업 중 병렬화할 수 없는 부분이 존재하면, 이 부분은 프로세서 수를 아무리 늘려도 실행 시간을 더 줄일 수 없다. 이는 암달의 법칙으로 정량화되는 근본적인 한계이다.

따라서 효과적인 병렬 알고리즘 설계는 가능한 한 많은 부분을 병렬화하여 순차적 부분의 비중을 줄이는 동시에, 통신과 부하 불균형으로 인한 오버헤드를 최소화하는 데 중점을 둔다. 속도 향상은 병렬 알고리즘의 효율성과 확장성을 논의하기 위한 출발점이 되는 핵심 지표이다.

병렬 알고리즘의 효율성은 주어진 하드웨어 자원을 얼마나 잘 활용하는지를 나타내는 척도이다. 단순히 속도가 빨라지는 것만으로는 충분하지 않으며, 사용된 프로세서 수에 비해 성능 향상이 얼마나 비례하는지를 평가하는 것이 중요하다.

효율성은 일반적으로 속도 향상을 사용된 프로세서 수로 나눈 값으로 정의된다. 즉, p개의 프로세서를 사용할 때 순차 알고리즘 대비 얻은 속도 향상이 S(p)라면, 효율성 E(p)는 S(p)/p로 계산된다. 이 값이 1에 가까울수록 이상적인 효율성을 가진다고 볼 수 있으며, 프로세서를 추가할 때마다 성능이 선형적으로 증가함을 의미한다. 효율성이 낮다는 것은 많은 프로세서가 유휴 상태이거나 통신 및 동기화로 인한 오버헤드가 크다는 것을 시사한다.

효율성에 영향을 미치는 주요 요인은 다음과 같다.

따라서 효율적인 병렬 알고리즘을 설계하려면 작업을 가능한 균등하게 분할하고, 프로세서 간 통신을 최소화하며, 알고리즘의 순차적 부분을 줄이는 것이 핵심이다. 이러한 고려 사항은 하드웨어 아키텍처(예: 공유 메모리, 분산 메모리)에 따라 그 전략이 달라진다.

병렬 알고리즘의 확장성은 시스템의 처리 자원(예: 프로세서 코어 수)이 증가할 때 알고리즘의 성능이 얼마나 비례적으로 향상되는지를 나타내는 척도이다. 이상적인 확장성을 가진 알고리즘은 자원이 n배 증가하면 실행 시간이 1/n로 줄어든다. 그러나 실제로는 통신 오버헤드, 동기화 비용, 작업 부하의 불균형, 공유 자원에 대한 경쟁 등의 요인으로 인해 확장성에 한계가 발생한다.

확장성은 크게 두 가지 관점에서 평가된다. 첫째는 강확장성으로, 문제의 크기는 고정한 채 프로세서 수만 증가시켰을 때의 성능 향상을 의미한다. 둘째는 약확장성으로, 프로세서 수가 증가함에 따라 문제의 크기도 비례적으로 증가시켰을 때의 성능 변화를 측정한다. 약확장성이 우수한 알고리즘은 더 큰 규모의 문제를 효율적으로 해결할 수 있는 능력을 가진다.

확장성을 저해하는 주요 요인은 다음과 같다.

따라서 확장성 있는 병렬 알고리즘을 설계하기 위해서는 데이터와 작업을 효율적으로 분할하고, 통신을 최소화하며, 동기화 지점을 줄이고, 부하를 균형 있게 분배하는 기법이 필요하다. 알고리즘의 확장성은 병렬 컴퓨팅 시스템의 규모가 커질수록 그 중요성이 더욱 부각된다.

암달의 법칙은 병렬 컴퓨팅에서 이론적인 속도 향상의 한계를 설명하는 법칙이다. 이 법칙은 프로그램의 일부만 병렬화할 수 있다는 점을 고려하여, 프로세서 수를 무한히 늘려도 달성할 수 있는 최대 속도 향상은 프로그램 내 순차적 부분의 크기에 의해 제한된다는 원리를 제시한다.

암달의 법칙의 공식은 다음과 같다.

이 공식에 따르면, 병렬화 가능한 부분(P)이 0%라면 속도 향상은 1배(즉, 향상 없음)이며, 병렬화 가능한 부분이 100%라면 이론상 속도 향상은 프로세서 수(N)에 비례한다. 그러나 실제로는 프로그램의 거의 모든 부분에 순차적으로 실행되어야 하는 코드가 존재하며, 이 순차적 부분(1-P)이 병렬 처리의 효율성에 결정적인 장벽이 된다.

따라서 암달의 법칙은 병렬 알고리즘 설계의 근본적인 교훈을 준다. 바로 순차적 부분을 최소화하는 것이 병렬 성능을 극대화하는 핵심이라는 점이다. 프로세서 수를 지나치게 늘리는 것보다 알고리즘을 재설계하여 병렬화 가능한 부분의 비율을 높이는 노력이 더 중요할 수 있다. 이 법칙은 병렬 컴퓨팅의 초기 시대에 제안되었지만, 멀티코어 프로세서가 보편화된 오늘날에도 시스템의 확장성을 예측하고 병목 현상을 이해하는 데 유용한 기본 원리로 남아 있다.

병렬 정렬 알고리즘은 정렬 문제를 여러 처리 요소에 분배하여 동시에 해결하는 알고리즘이다. 순차 정렬 알고리즘을 병렬화하거나 처음부터 병렬 실행을 고려하여 설계된다. 핵심은 데이터를 여러 부분으로 나누어 각 부분을 병렬로 정렬한 후, 효율적으로 병합하는 것이다. 대표적인 병렬 정렬 알고리즘으로는 병렬 합병 정렬, 병렬 퀵 정렬, 병렬 샘플 정렬 등이 있다.

병렬 합병 정렬은 분할 정복 패러다임을 따르는 대표적인 예시이다. 알고리즘은 먼저 정렬할 데이터를 여러 프로세서에 균등하게 분할한다. 각 프로세서는 자신에게 할당된 데이터 조각을 로컬에서 순차적으로 정렬한다. 이후, 정렬된 데이터 조각들을 쌍으로 병합하는 과정을 트리 구조를 따라 병렬로 수행하여 최종 정렬된 결과를 얻는다. 이 과정에서 병합 단계의 효율적인 병렬화가 성능을 결정한다.

병렬 퀵 정렬은 피벗 선택과 분할 단계에서 병렬성을 활용한다. 여러 프로세서가 협력하여 피벗을 선택하거나, 데이터를 피벗을 기준으로 여러 부분 집합으로 분할하는 작업을 동시에 수행할 수 있다. 분할 후 생성된 부분 집합들은 독립적으로 정렬될 수 있어 자연스러운 병렬성을 제공한다. 그러나 피벗 선택의 불균형이 성능에 큰 영향을 미칠 수 있어, 병렬 환경에서는 균형 잡힌 분할을 보장하는 전략이 중요하다.

이러한 알고리즘의 성능은 사용되는 병렬 프로그래밍 모델에 따라 구현 방식이 달라진다. 공유 메모리 시스템에서는 스레드 간 작업 분할과 동기화를 통해 구현되는 반면, 분산 메모리 시스템에서는 데이터 분배와 프로세스 간 통신을 통해 구현된다. 성공적인 병렬 정렬은 작업 부하의 균형, 프로세서 간 통신 최소화, 그리고 효율적인 동기화를 달성하는 데 달려 있다.

병렬 그래프 알고리즘은 대규모 그래프 데이터를 효율적으로 처리하기 위해 여러 처리 장치에 계산을 분배한다. 그래프의 구조는 본질적으로 불규칙하고 데이터 의존성이 복잡하여 병렬화에 특별한 기법이 필요하다. 대표적인 접근법으로는 정점 중심 프로그래밍 모델과 간선 중심 프로그래밍 모델이 있으며, 이를 통해 그래프 탐색, 최단 경로 탐색, 연결 요소 찾기 등의 문제를 해결한다.

병렬 그래프 알고리즘의 주요 예로는 병렬 너비 우선 탐색(BFS)이 있다. 이 알고리즘은 현재 탐색 중인 경계 정점 집합을 여러 스레드나 프로세스가 나누어 처리하며, 다음 레벨의 정점을 동시에 발견한다. 이를 구현할 때는 중복 방문을 방지하기 위한 동기화와 효율적인 큐 관리가 중요하다. 또 다른 중요한 예는 페이지랭크와 같은 그래프 순위 알고리즘으로, 행렬-벡터 곱셈의 반복 계산을 병렬 분산 환경에서 수행한다.

이러한 알고리즘들은 분산 메모리 시스템에서는 메시지 전달 인터페이스를, 공유 메모리 시스템에서는 쓰레드와 잠금 매커니즘을 활용한다. 성공적인 병렬화의 핵심은 계산 부하를 고르게 분배하고 프로세서 간의 통신 및 동기화 비용을 최소화하는 데 있다. 그래프의 크기와 형태에 따라 적합한 병렬 전략이 달라지므로, 알고리즘 설계 시 확장성과 부하 균형을 고려해야 한다.

행렬 연산은 병렬 처리에 매우 적합한 분야이다. 행렬의 덧셈, 곱셈, 전치, 역행렬 계산, 고유값 문제 등 많은 연산이 독립적인 부분 연산으로 분해될 수 있어, 여러 프로세서가 동시에 작업을 수행할 수 있다.

행렬 곱셈은 대표적인 병렬 알고리즘 사례이다. 두 행렬 A와 B를 곱할 때, 결과 행렬 C의 각 요소는 A의 한 행과 B의 한 열의 내적으로 계산된다. 각 요소의 계산은 서로 독립적이므로, 모든 요소를 서로 다른 프로세서에 할당하여 동시에 계산할 수 있다. 더 효율적인 방법으로는 행렬을 블록으로 분할한 후 블록 간의 곱셈을 병렬로 수행하는 방법이 널리 사용된다. 이는 분할 정복 기법의 일종이며, 캐시 메모리 활용도와 통신 효율성을 높인다.

병렬 행렬 연산은 다양한 하드웨어 아키텍처에서 구현된다. 공유 메모리 시스템에서는 OpenMP를 사용하여 루프를 병렬화하는 방식이 일반적이다. 반면, 대규모 분산 메모리 시스템이나 클러스터 컴퓨팅 환경에서는 MPI를 활용하여 프로세스 간에 행렬 블록을 분배하고 통신한다. 또한, GPU는 수많은 코어를 이용하여 행렬 연산을 위한 데이터 병렬 처리를 극도로 가속화하며, CUDA나 OpenCL 같은 플랫폼을 통해 프로그래밍된다.

[3] 캐논 알고리즘: 행렬 블록을 순환 이동시켜 통신 오버헤드를 줄이는 분산 메모리용 행렬 곱셈 알고리즘.

[4] 폭스 알고리즘: 브로드캐스트와 순환 이동을 결합한 또 다른 분산 행렬 곱셈 알고리즘.

수치 해석은 수학적 문제를 컴퓨터를 이용해 근사적으로 해결하는 분야이다. 병렬 알고리즘은 수치 해석에서 계산 집약적인 문제를 효율적으로 처리하기 위해 핵심적으로 활용된다. 특히 대규모 선형 시스템의 해를 구하거나, 편미분 방정식을 수치적으로 풀고, 고유값 문제를 계산하는 데 병렬 처리가 필수적이다.

병렬 수치 해석의 대표적인 예로는 선형대수 연산이 있다. 행렬 곱셈이나 선형 시스템 풀이를 위한 알고리즘은 작업을 여러 처리 장치에 분배하기에 적합한 구조를 가진다. 예를 들어, 행렬을 블록으로 분할하여 각 블록의 연산을 다른 프로세서에 할당하는 방식이 널리 사용된다. 이를 통해 방대한 크기의 행렬 계산 시간을 크게 단축할 수 있다.

편미분 방정식(PDE)의 수치 해법 또한 병렬화의 주요 대상이다. 유한 차분법이나 유한 요소법을 사용할 때, 계산 영역을 여러 부분 영역으로 분할하여 각 영역의 계산을 다른 프로세서가 담당하게 하는 영역 분할 기법이 효과적이다. 각 프로세서는 자신의 영역을 계산한 후, 경계 정보를 이웃한 프로세서와 교환하여 전체 해를 구성한다.

이러한 병렬 수치 알고리즘은 멀티코어 프로세서, GPU, 또는 클러스터 컴퓨팅 환경에서 MPI나 OpenMP, CUDA와 같은 도구를 이용해 구현된다. 알고리즘 설계 시에는 계산 작업의 균등한 분배와 프로세서 간의 통신 오버헤드를 최소화하는 것이 성능 향상의 관건이다.

멀티코어 프로세서는 단일 물리적 칩 안에 두 개 이상의 독립적인 실행 코어를 통합한 중앙 처리 장치(CPU)이다. 각 코어는 별도의 명령어 스트림을 처리할 수 있어, 여러 작업을 진정한 의미에서 동시에 실행하는 병렬 처리가 가능해진다. 이는 단일 코어 프로세서가 클록 속도 향상에 의존하던 기존 방식에서 벗어나, 전력 소비와 발열 문제를 해결하면서도 성능을 높이는 핵심적인 하드웨어 발전이다. 멀티코어 아키텍처는 병렬 알고리즘이 실제로 실행되는 가장 일반적인 플랫폼이 되었다.

멀티코어 시스템은 주로 공유 메모리 모델을 기반으로 한다. 모든 코어가 단일 물리적 메모리 공간을 공유하며, 이를 통해 데이터를 교환하고 협력한다. 이 모델에서는 동기화가 중요한 도전 과제로 부상한다. 여러 코어가 동일한 메모리 위치에 동시에 접근하려 할 때 데이터 불일치가 발생하지 않도록 락, 세마포어, 원자적 연산 등의 메커니즘을 사용하여 조정해야 한다. 이러한 특성 때문에 멀티코어 환경을 위한 병렬 알고리즘은 데이터 경쟁을 피하고 공유 자원에 대한 접근을 효율적으로 관리하도록 설계되어야 한다.

멀티코어 프로세서의 성능을 최대한 활용하기 위해서는 소프트웨어 측면의 지원이 필수적이다. 운영체제는 여러 스레드를 서로 다른 코어에 스케줄링하여 병렬성을 실현한다. 또한, OpenMP와 같은 병렬 프로그래밍 API는 개발자가 컴파일러 지시문을 추가하는 비교적 간단한 방식으로 공유 메모리 병렬 프로그램을 작성할 수 있게 돕는다. 멀티코어의 등장은 데스크톱과 서버 컴퓨팅의 표준을 바꾸었으며, 병렬 처리를 일상적인 프로그래밍의 고려 사항으로 만들었다.

GPU는 그래픽 처리 장치의 약자로, 본래 컴퓨터 그래픽스 렌더링을 가속하기 위해 설계된 특수한 하드웨어이다. 그러나 현대의 GPU는 수천 개의 작고 효율적인 코어를 집적하여 대규모 데이터 병렬 작업을 처리하는 데 매우 적합한 구조를 가지고 있어, 범용 병렬 컴퓨팅 프로세서로 널리 활용되고 있다. 이러한 용도를 일반적으로 GPGPU라고 부른다. CPU가 복잡한 제어 흐름과 순차적 작업에 최적화된 소수의 강력한 코어를 갖는 반면, GPU는 상대적으로 단순한 연산을 동시에 수행하는 방대한 수의 코어를 가지고 있어 행렬 연산, 이미지 처리, 과학 시뮬레이션, 머신러닝 학습과 같은 계산 집약적 문제를 가속하는 데 효과적이다.

GPU의 병렬 처리 아키텍처는 주로 SIMD 또는 SIMT 방식으로 작동한다. 이는 단일 명령어가 다중 데이터 스트림에 동시에 적용되는 방식을 의미한다. 예를 들어, 하나의 연산 명령이 GPU의 수백 개의 코어에 브로드캐스트되어 각 코어는 서로 다른 데이터 요소에 대해 동일한 연산을 병렬로 수행한다. 이러한 구조는 규칙적인 데이터 구조(예: 배열, 행렬)에 대한 동일한 연산을 반복하는 작업에 특히 효율적이다.

GPU를 이용한 병렬 프로그래밍을 위해서는 특수한 도구와 프로그래밍 모델이 필요하다. 대표적으로 NVIDIA의 GPU를 위한 CUDA와 다양한 벤더의 GPU를 지원하는 OpenCL이 있다. 이러한 플랫폼들은 개발자가 호스트(CPU)와 디바이스(GPU) 간의 메모리 관리와 코드 실행을 제어할 수 있게 하여, 병렬 알고리즘을 GPU 하드웨어에 효율적으로 매핑할 수 있도록 한다. 또한 딥러닝 프레임워크들은 이러한 GPU 가속 라이브러리를 백엔드로 활용하여 모델 학습 속도를 획기적으로 높인다.

클러스터 컴퓨팅은 병렬 컴퓨팅을 구현하는 주요 하드웨어 아키텍처 중 하나이다. 이는 네트워크로 연결된 여러 대의 독립적인 컴퓨터(노드)를 하나의 시스템처럼 동작하도록 통합하여, 단일 컴퓨터로는 처리하기 어려운 대규모 계산 문제를 해결한다. 각 노드는 일반적으로 자체 운영 체제, 메모리, 프로세서를 가지며, 메시지 전달 방식(주로 MPI와 같은 라이브러리 활용)을 통해 통신하는 분산 메모리 모델을 기반으로 한다.

클러스터는 구성 방식과 목적에 따라 여러 유형으로 구분된다. 고성능 컴퓨팅(HPC) 클러스터는 과학적 시뮬레이션이나 복잡한 수치 해석과 같은 계산 집약적 작업을 수행하는 데 특화되어 있다. 반면, 고가용성 클러스터는 서버 장애 시 중단 없는 서비스를 제공하기 위해 구축되며, 로드 밸런싱 클러스터는 많은 수의 사용자 요청을 여러 노드에 분산하여 처리한다.

클러스터 컴퓨팅의 주요 장점은 높은 확장성과 비용 효율성이다. 필요에 따라 상용 서버나 워크스테이션을 추가하여 성능을 증설할 수 있으며, 고가의 전용 슈퍼컴퓨터에 비해 상대적으로 구축 비용이 낮다. 그러나 노드 간 통신 지연과 네트워크 대역폭 한계는 성능에 영향을 미치는 주요 도전 과제이다. 이를 극복하기 위해 고속 상호 연결 네트워크(인피니밴드 등)를 사용하고, 통신을 최소화하는 알고리즘을 설계하는 것이 중요하다.

클러스터는 현대 병렬 처리의 핵심 인프라로, 대규모 데이터 분석(빅데이터), 기계 학습 모델 훈련, 날씨 예측, 유전체 분석 등 다양한 분야에서 널리 활용된다.

슈퍼컴퓨터는 일반적인 개인용 컴퓨터나 서버보다 훨씬 뛰어난 계산 성능을 제공하는 고성능 컴퓨터 시스템이다. 이들은 주로 과학 연구, 공학 시뮬레이션, 기상 예측, 암호 해독, 복잡한 물리적 현상 모델링 등 대규모 계산이 필요한 첨단 분야에서 사용된다. 슈퍼컴퓨터의 성능은 초당 수행할 수 있는 부동소수점 연산 횟수(FLOPS)로 측정하며, 현대의 최상위 슈퍼컴퓨터는 엑사플롭스(10^18 FLOPS) 단위의 성능을 가진다.

슈퍼컴퓨터의 아키텍처는 대규모 병렬 처리를 핵심으로 한다. 이는 수천에서 수백만 개의 처리 코어를 하나의 시스템으로 통합하여 구성된다. 이러한 코어들은 고속의 상호 연결 네트워크를 통해 결합되어, 하나의 거대한 병렬 컴퓨팅 자원으로 작동한다. 대표적인 구성 방식으로는 수만 개의 범용 프로세서를 클러스터 형태로 연결하는 방식과, 범용 CPU에 수많은 코어를 가진 GPU나 다른 가속기를 결합하는 이종 컴퓨팅 방식이 있다.

슈퍼컴퓨터는 병렬 알고리즘의 극한적인 적용 사례이다. 이들 시스템에서 효율적으로 실행되기 위해서는 알고리즘이 높은 수준의 병렬성을 가지고 있어야 하며, 방대한 양의 프로세서 간 통신과 데이터 이동을 최소화하도록 설계되어야 한다. 또한, 메모리 계층 구조와 대용량 I/O 처리에 대한 고려도 필수적이다. 슈퍼컴퓨터의 성능은 하드웨어뿐만 아니라 이러한 병렬 알고리즘과 소프트웨어의 효율성에 크게 의존한다.

슈퍼컴퓨터 분야는 지속적인 발전을 거듭하고 있으며, 에너지 효율성(성능 대비 전력 소비)과 프로그래밍의 용이성도 중요한 도전 과제로 대두되고 있다.

OpenMP는 공유 메모리 시스템을 위한 병렬 프로그래밍 API이다. 주로 C, C++, 포트란 언어를 지원하며, 컴파일러 지시문, 라이브러리 루틴, 환경 변수를 사용하여 병렬 처리를 구현한다. 개발자가 순차 코드에 지시문을 추가하는 방식으로 점진적인 병렬화가 가능하여 접근성이 높다. 이는 멀티코어 CPU와 같은 공유 메모리 아키텍처에서 작업을 여러 스레드로 분할하여 실행하는 데 적합하다.

OpenMP의 핵심은 병렬 영역을 생성하는 것이다. #pragma omp parallel 지시문을 사용하면 이후의 구조화된 블록 코드가 여러 스레드에 의해 동시에 실행된다. 스레드 수는 환경 변수나 런타임 라이브러리 함수로 제어할 수 있다. 또한, for, sections, single 같은 작업 분할 지시문을 제공하여 루프 병렬화나 독립적인 작업 구역을 정의할 수 있다.

동기화와 데이터 공유는 중요한 고려 사항이다. OpenMP는 critical, atomic, barrier 같은 지시문으로 스레드 간의 동기화를 보장한다. 변수의 공유 속성은 shared, private, firstprivate, lastprivate 등의 절로 명시적으로 지정하여 데이터 경쟁 조건을 방지한다. 이를 통해 개발자는 메모리 일관성을 유지하면서 병렬 실행을 관리할 수 있다.

OpenMP는 비교적 낮은 진입 장벽으로 인해 학계와 산업계에서 널리 사용되며, 멀티코어 프로세서의 성능을 활용하는 표준적인 도구 중 하나이다.

MPI는 메시지 전달 인터페이스의 약자로, 분산 메모리 병렬 컴퓨팅 시스템에서 프로세스 간 통신을 위한 표준화된 라이브러리 규격이다. 주로 클러스터나 슈퍼컴퓨터와 같은 다중 노드 시스템에서 병렬 프로그램을 작성하는 데 널리 사용된다. MPI는 공유 메모리를 가정하지 않고, 명시적인 메시지 송수신을 통해 데이터를 교환하므로, 대규모 병렬 시스템에 적합하다.

MPI의 핵심은 통신자와 통신 작업 관리에 있다. 통신자는 MPI_COMM_WORLD와 같은 그룹으로, 프로그램에 참여하는 모든 프로세스를 포함한다. 주요 통신 작업으로는 점대점 통신과 집합 통신이 있다. 점대점 통신은 한 프로세스가 다른 특정 프로세스로 데이터를 직접 보내는 방식이며, 집합 통신은 브로드캐스트, 리듀스, 게더 등 그룹 내 모든 프로세스가 참여하는 작업을 말한다.

MPI를 사용한 프로그래밍의 일반적인 구조는 다음과 같다. 먼저 MPI_Init으로 환경을 초기화하고, MPI_Comm_size와 MPI_Comm_rank로 전체 프로세스 수와 각 프로세스의 고유 번호(랭크)를 얻는다. 그 후, 알고리즘에 따라 데이터를 분할하고, 필요한 메시지 통신을 수행하며, 마지막으로 MPI_Finalize로 자원을 정리한다. 이 모델은 각 프로세스가 독립된 메모리 공간을 가지므로, 데이터 분배와 동기화를 프로그래머가 직접 설계해야 한다.

MPI는 여러 구현체가 존재하며, Open MPI와 MPICH가 대표적이다. 이러한 구현체들은 표준 MPI 규격을 준수하면서도 다양한 네트워크 하드웨어와 운영체제를 지원한다. MPI는 높은 확장성과 이식성을 제공하지만, 메시지 전달에 따른 오버헤드와 데드락 같은 동기화 문제를 주의 깊게 관리해야 하는 도전 과제도 있다.

CUDA는 엔비디아가 개발한 병렬 컴퓨팅 플랫폼이자 프로그래밍 모델이다. 주로 엔비디아 GPU를 사용하여 범용 연산을 수행하는 GPGPU를 위한 환경을 제공한다. CUDA를 사용하면 C, C++, 포트란과 같은 언어를 확장하여 GPU의 수많은 코어를 활용한 병렬 처리를 프로그래밍할 수 있다. 이는 특히 대규모 데이터를 다루거나 동일한 연산을 많은 요소에 반복 적용해야 하는 작업에서 높은 성능 향상을 가져온다.

CUDA의 실행 모델은 호스트(CPU)와 디바이스(GPU)로 구성된다. 프로그램의 주요 부분은 호스트에서 실행되며, 병렬 처리가 필요한 계산 집약적인 커널 함수는 디바이스에서 실행된다. 커널은 수백에서 수천 개의 스레드로 구성된 그리드에서 실행되며, 이러한 스레드들은 블록으로 그룹화되어 GPU의 스트리밍 멀티프로세서에 할당된다. 이 계층적 구조를 통해 하드웨어 리소스를 효율적으로 관리하고 메모리 접근을 최적화할 수 있다.

CUDA의 메모리 계층은 여러 계층으로 나뉜다. 각 스레드는 전용 레지스터와 로컬 메모리를 가지며, 각 스레드 블록은 공유 메모리를, 모든 스레드는 전역 메모리에 접근할 수 있다. 공유 메모리는 블록 내 스레드 간 통신에 사용되며 전역 메모리보다 훨씬 빠르기 때문에, 알고리즘 설계 시 데이터를 공유 메모리에 캐싱하는 것이 성능에 결정적이다.

CUDA는 행렬 곱셈, 정렬, 몬테카를로 시뮬레이션, 딥러닝 학습과 같은 다양한 병렬 알고리즘 구현에 널리 사용된다. 성공적인 CUDA 프로그래밍을 위해서는 알고리즘의 병렬성과 데이터 지역성을 잘 활용하고, 메모리 접근 패턴을 최적화하며, 디바이스의 하드웨어 제약을 고려해야 한다.

OpenCL은 Open Computing Language의 약자로, 이종 컴퓨팅 플랫폼에서 병렬 프로그램을 작성하기 위한 개방형 표준 프레임워크이다. CPU, GPU, DSP, FPGA 등 다양한 프로세서를 포함하는 이종 시스템에서 데이터 병렬 및 태스크 병렬 컴퓨팅을 지원한다. OpenCL은 단일한 프로그래밍 모델을 제공하여 개발자가 다양한 하드웨어 아키텍처에 맞춰 효율적인 병렬 코드를 작성할 수 있게 한다.

OpenCL의 핵심은 플랫폼 모델, 실행 모델, 메모리 모델, 프로그래밍 모델로 구성된다. 플랫폼 모델은 호스트(일반적으로 CPU)와 하나 이상의 컴퓨팅 디바이스(예: GPU)로 시스템을 정의한다. 실행 모델에서는 호스트가 커널이라는 함수를 디바이스에서 실행하며, 이 커널은 다수의 작업 항목으로 병렬 처리된다. 메모리 모델은 계층적 메모리 공간(전역, 지역, 상수, 개인 메모리)을 명시하여 데이터 배치와 접근 패턴을 최적화하는 데 도움을 준다.

OpenCL은 C 언어를 기반으로 한 커널 언어를 사용하며, 플랫폼 독립성을 강점으로 한다. 주요 구성 요소는 다음과 같다.

OpenCL은 과학 계산, 이미지 처리, 머신러닝 등 다양한 병렬 컴퓨팅 분야에서 활용된다. 특히 OpenMP나 CUDA와 비교할 때, 특정 제조사에 종속되지 않고 다양한 하드웨어를 지원하는 범용성이 특징이다. 그러나 하드웨어 간 최적화와 성능 추출을 위해서는 각 디바이스의 아키텍처를 고려한 세밀한 튜닝이 필요하다.

동기화는 병렬 알고리즘에서 두 개 이상의 스레드나 프로세스가 공유 자원에 접근하거나 실행 순서를 조정할 때 발생하는 문제를 관리하는 기법이다. 병렬 실행의 핵심은 작업을 분할하여 동시에 처리하는 것이지만, 이러한 작업들이 서로 독립적이지 않고 데이터를 공유하거나 특정 순서로 실행되어야 할 경우, 올바른 결과를 보장하기 위해 동기화가 필수적이다. 동기화가 제대로 이루어지지 않으면 경쟁 조건, 교착 상태, 기아 상태와 같은 문제가 발생하여 알고리즘의 정확성과 성능을 크게 저해할 수 있다.

병렬 프로그래밍 모델에 따라 동기화의 접근 방식이 달라진다. 공유 메모리 모델에서는 여러 스레드가 같은 메모리 공간을 공유하므로, 뮤텍스, 세마포어, 모니터, 원자적 연산과 같은 동기화 프리미티브를 사용하여 임계 구역에 대한 상호 배제를 보장한다. 반면, 분산 메모리 모델에서는 프로세스 간에 메모리가 공유되지 않으므로, 메시지 패싱을 통한 명시적인 통신(예: 장벽 동기화, 집합 통신)으로 실행 흐름을 조정한다.

동기화는 병렬 알고리즘의 성능에 직접적인 영향을 미친다. 과도한 동기화는 대기 시간을 증가시켜 병렬 실행의 이점을 상쇄할 수 있으며, 특히 암달의 법칙에 따라 순차적 부분이 성능 향상의 병목이 될 수 있다. 따라서 효율적인 병렬 알고리즘 설계에서는 동기화의 필요성을 최소화하거나, 비차단 알고리즘, 잠금 없는 데이터 구조와 같은 고급 기법을 활용하여 경쟁을 줄이는 방향으로 접근한다. 이는 부하 균형 및 통신 오버헤드 관리와 함께 병렬 알고리즘의 주요 도전 과제 중 하나를 이룬다.

병렬 알고리즘에서 부하 균형은 전체 시스템의 성능을 최대화하기 위해 여러 프로세서나 스레드 간에 작업을 고르게 분배하는 과정이다. 이상적인 병렬 실행에서는 모든 처리 요소가 거의 동시에 작업을 완료하여 유휴 시간을 최소화한다. 그러나 작업의 크기나 복잡도가 균일하지 않거나, 데이터 의존성으로 인해 특정 작업이 다른 작업의 결과를 기다려야 하는 경우, 일부 프로세서는 일을 빨리 끝내고 대기 상태에 머무르는 반면 다른 프로세서는 여전히 바쁘게 작업할 수 있다. 이러한 불균형은 전체 실행 시간을 늘리고 병렬화의 이점을 감소시킨다.

부하 균형 기법은 크게 정적 부하 균형과 동적 부하 균형으로 나뉜다. 정적 부하 균형은 실행 전에 작업의 특성과 시스템 자원을 분석하여 미리 작업을 할당하는 방식이다. 이는 런타임 오버헤드가 거의 없지만, 작업 소요 시간을 정확히 예측하기 어렵거나 실행 중 상황이 변할 경우 비효율적일 수 있다. 반면, 동적 부하 균형은 실행 중에 각 프로세서의 작업 부하를 모니터링하고, 작업이 일찍 끝난 프로세서(일꾼)가 다른 바쁜 프로세서로부터 작업을 가져와 수행하는 방식이다. 이는 작업 부하의 불균형을 실시간으로 조정할 수 있지만, 작업 재분배와 관련된 통신 및 동기화 오버헤드가 발생한다.

효과적인 부하 균형을 구현하기 위해 다양한 전략이 사용된다. 작업 풀 모델은 중앙 또는 분산된 큐에 작업을 저장하고 유휴 상태의 워커가 큐에서 작업을 가져가는 방식으로 동적 분배를 용이하게 한다. 분할 정복 알고리즘에서는 작업을 재귀적으로 세분화하여 여러 프로세서에 할당할 수 있으며, 큰 작업을 더 작은 단위로 나누어 부하를 고르게 퍼뜨린다. 또한, 분산 메모리 시스템에서는 작업 도용 기법이 널리 쓰이는데, 일찍 일을 마친 프로세서가 이웃 프로세서의 작업 큐에서 작업을 "훔쳐"와서 실행함으로써 균형을 맞춘다.

부하 균형의 성공은 알고리즘의 특성, 하드웨어 아키텍처, 통신 비용 등 여러 요소에 좌우된다. 따라서 병렬 알고리즘을 설계할 때는 작업 분할의 단위와 빈도, 프로세서 간 통신 패턴, 동기화 메커니즘 등을 신중히 고려하여 전체 처리량을 높이고 대기 시간을 줄여야 한다.

데이터 의존성은 병렬 알고리즘 설계와 실행에서 핵심적인 제약 조건이다. 이는 서로 다른 작업이나 프로세스가 데이터를 공유할 때, 하나의 작업 결과가 다른 작업의 입력이나 실행 조건에 영향을 미치는 관계를 의미한다. 이러한 의존성이 존재하면, 작업들은 완전히 독립적으로 실행될 수 없으며, 특정 순서나 동기화가 필요해져 병렬 처리의 효율성을 저해할 수 있다.

데이터 의존성은 주로 세 가지 유형으로 구분된다. 첫째, 흐름 의존성은 한 작업이 생성한 데이터를 다른 작업이 사용하는 경우이다. 둘째, 반 의존성은 한 작업이 데이터를 읽은 후 다른 작업이 그 데이터를 수정하는 경우이다. 셋째, 출력 의존성은 두 개 이상의 작업이 동일한 데이터 위치에 결과를 쓰려고 하는 경우이다. 이러한 의존성은 특히 공유 메모리 모델에서 동기화 문제와 경쟁 조건을 발생시키는 주요 원인이 된다.

병렬 알고리즘 설계 시 데이터 의존성을 해결하는 기법이 필요하다. 일반적인 접근법은 의존성이 있는 작업들을 동일한 프로세서나 스레드에 할당하거나, 의존성 제거를 위해 알고리즘을 재구성하는 것이다. 예를 들어, 루프 분할 시 반복문 간 데이터 의존성이 없다면 쉽게 병렬화할 수 있지만, 의존성이 있다면 파이프라이닝이나 재귀적 분할 같은 다른 병렬 패턴을 적용해야 한다. 데이터 의존성 분석은 컴파일러의 자동 병렬화나 프로그래머의 수동 최적화에서 중요한 단계이다.

데이터 의존성은 병렬 처리의 이론적 한계를 규정하며, 암달의 법칙에서 지적하는 순차적 부분의 대부분을 구성한다. 따라서 효율적인 병렬 알고리즘은 가능한 한 데이터 의존성을 최소화하고, 불가피한 의존성은 효율적으로 관리하는 방향으로 설계된다.

통신 오버헤드는 병렬 알고리즘에서 프로세서나 스레드 간에 데이터를 교환하거나 동기화하기 위해 소요되는 추가적인 시간과 자원을 의미한다. 이는 순수한 계산 시간 외에 발생하는 비용으로, 병렬 시스템의 성능을 저하시키는 주요 요인 중 하나이다. 특히 분산 메모리 시스템이나 대규모 클러스터 컴퓨팅 환경에서는 통신 지연이 전체 실행 시간에 큰 영향을 미칠 수 있다.

통신 오버헤드는 주로 네트워크 대역폭, 지연 시간, 그리고 프로세서 간의 메시지 전송 빈도와 크기에 의해 결정된다. 알고리즘 설계 시 계산 작업을 여러 부분으로 분할하면 할수록 부분 결과를 합치거나 다른 프로세서와 공유하기 위한 통신이 증가하게 된다. 따라서 이상적인 병렬화는 계산량을 균등하게 분배하면서도 통신을 최소화하는 방향으로 이루어져야 한다.

통신 오버헤드를 줄이기 위한 일반적인 기법은 다음과 같다.

병렬 알고리즘의 성능 분석에서 통신 오버헤드는 반드시 고려되어야 한다. 높은 통신 오버헤드는 암달의 법칙에 따른 이론적 속도 향상을 제한하며, 시스템의 확장성을 떨어뜨린다. 따라서 효율적인 병렬 알고리즘은 계산 작업의 분배와 통신 요구사항 사이의 균형을 적절히 맞추는 것이 중요하다.